/*

https://leetcode.cn/problems/longest-substring-without-repeating-characters/submissions/560518517/
*/
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();  // 获取字符串的长度
        if (n == 0) return 0;  // 如果字符串为空，直接返回 0

        // 初始化变量
        int pre = 1;  // 上一个位置的最长无重复子串长度
        int dp = 1;   // 当前位置的最长无重复子串长度
        int ans = 1;  // 记录全局最长无重复子串长度

        // 哈希表，记录每个字符上次出现的位置，初始值为 0
        vector<int> dict(257, 0);
        dict[s[0]] = 1;  // 第一个字符的位置设为 1

        // 从第二个字符开始遍历
        for (int i = 1; i < n; ++i) {
            // 计算当前位置的最长无重复子串长度
            dp = min(i + 1 - dict[s[i]], pre + 1);  // 选择较小的长度
            dict[s[i]] = i + 1;  // 更新当前字符的位置
            pre = dp;  // 更新上一个位置的最长无重复子串长度
            ans = max(ans, dp);  // 更新全局最长无重复子串长度
        }

        return ans;  // 返回最终结果
    }
};